今天要面對的問題是 Sort an Array，一句話解釋呢，就是把拿到的陣列依照大小排列好，然後傳回去。這個問題用 javascript 超級簡單，不信你看：

var sortArray = function(nums) {
    return nums.sort((a,b) => {return a - b})
};

好好運用內建的函式，效能在 75% 左右，記憶體表現差了一點，但也有 50%，勉勉強強還可以？

好啦，雖然這個懶人解法不差，但不是今天要講的內容。今天要分享的解法叫 Divide and Conquer。簡單來說，就是把大問題切成小問題，小問題解完後再組裝回去。假設今天要排序的陣列有 1000 個元素，想想就覺得頭痛。所以我們可以把陣列切成一半，再一半，再一半，一直切到剩下兩個元素就很好排了。排完後就要開始組裝，於是我們先拿兩組來組成有四元素的陣列，然後再拿兩個四元素的組成八元素的陣列，這樣慢慢拼回去。

上面的解法雖然直觀，但效率沒那麼好。排序算法有很多，裡面有個好用的東西叫快速排序，它的方法是：先找一個錨點放中間，比它小的丟左邊，比它大的丟右邊。做完後，我們得到左右兩邊沒排過的子陣列。接著進行一樣的動作，找新錨點，分類，分好後繼續切，切到沒有就完成了。

這個方法還有進化版，就是拿兩個指針，一個從頭開始找比錨點大的數字，一個從最後開始找比錨點小的，當兩邊各找到一個時，就把兩個數字的位置交換，然後繼續。當兩個指針重疊時，就表示完成第一次分類。這種方式的好處是不用另外拿一個陣列來存結果，只在原本的陣列進行交換，而且可以把交換的次數降到最低。

最後，附上官方版統計數據頁的參考解法，寫不出來所以我們一起膜拜大神們吧QQ

// javascript
var sortArray = function(nums) {
  quickSort(nums, 0, nums.length - 1)
  return nums
};

let quickSort = (arr, start, end) => {
  if (start >= end) return
  let index = partition(arr, start, end)
  quickSort(arr, start, index - 1)
  quickSort(arr, index, end)
}

// quick
let partition = (arr, start, end) => {
  let midIndex = Math.floor(start + (end - start) / 2)
  let mid = arr[midIndex]
  let i = start
  let j = end
  
  while (i <= j) {
    while (arr[i] < mid) i++
    while (arr[j] > mid) j--
    
    if (i <= j) {
      swap(arr, i, j)
      i++
      j--
    }
  }
  return i
}

let swap = (arr, a, b) => {
  let temp = arr[a]
  arr[a] = arr[b]
  arr[b] = temp
}